#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

//K
#define N_QUEENS 30

#define N_ITERATIONS 10000

int queens_columns[N_QUEENS];

void makeRandomInitBoard(void) {
	int i;
	for (i = 0; i < N_QUEENS; i++){
		queens_columns[i] = rand() % N_QUEENS;
	}
}

int get_number_of_collisions(void){
	int queen;
	int collisions = 0;

	for(queen = 0; queen < N_QUEENS; queen++){
		int other_queen;
		for(other_queen = 0; other_queen < N_QUEENS; other_queen++){
			if (other_queen == queen){
				continue;
			}
			if(queens_columns[other_queen] == queens_columns[queen]){
				collisions++;
			}
			else if(queens_columns[other_queen] == (queens_columns[queen] + abs(queen - other_queen))){
				collisions++;
			}
			else if(queens_columns[other_queen] == (queens_columns[queen] - abs(queen - other_queen))){
				collisions++;
			}
		}
	}
	return collisions;
}

int min_conflicts_for_a_queen(int queen) {
	int column;
	int best_column;
	int collisions_in_best_column = N_QUEENS+1;
	for(column = 0; column < N_QUEENS; column++){
		int collisions = 0;
		int other_queen;
		for(other_queen = 0; other_queen < N_QUEENS; other_queen++){
			if (other_queen == queen){
				continue;
			}
			if(queens_columns[other_queen] == column){
				collisions++;
			}
			else if(queens_columns[other_queen] == (column + abs(queen - other_queen))){
				collisions++;
			}
			else if(queens_columns[other_queen] == (column - abs(queen - other_queen))){
				collisions++;
			}
		}
		if(collisions < collisions_in_best_column){
			best_column = column;
			collisions_in_best_column = collisions;
		}
		//If the new column is as good as the old we have a 50 % chance of using it
		else if(collisions == collisions_in_best_column && rand()%10 < 5){
			best_column = column;
		}
	}

	return best_column;
}

void printBoard(void){
	int i,j;
	for(i = 0; i < N_QUEENS; i++){
		for(j = 0; j < N_QUEENS; j++){
			cout << "|";
			if(queens_columns[i] == j){
				cout << "X";
			}else{
				cout << " ";
			}
		}
		cout << "|" << endl;
	}
}

int main(int argc, char **argv) {
	srand ( time(NULL) );
	// Init board with random K queens
	// Repeat for either a maximum number of steps or until a violation-free solution is found:
	//	(a) Randomly choose a queen
	//	(b) Use MIN-CONFLICTS to choose a new column for the queen. Only if ALL columns would produce MORE violations than
	//		does the current column, should the queen stay put

	makeRandomInitBoard();
	
//	printBoard();

//	cout << "hei" << min_conflicts_for_a_queen(3) << endl;


	bool success = false;

	int i;
	for(i = 0; i < N_ITERATIONS; i++){
		
		//Check if correct solution
		int collisions = get_number_of_collisions();

		if (collisions == 0){
			success = true;
			break;
		}


		int current_queen = rand() % N_QUEENS;

		int best_column = min_conflicts_for_a_queen(current_queen);
		
		cout << "Iteration: " << i << endl;
		cout << "Queen " << current_queen << "will be moved to " << best_column << endl;

		queens_columns[current_queen] = best_column;

		printBoard();
		
	}

	if(success){
		cout << "YEEY!" << endl;
	}
	else{
		cout << "BOOO!" << endl;
	}

	cout << "Number of iterations: " << i << endl;

	printBoard();


	return 0;
}
